
// 有n个元素，元素的值范围在0 ~ n-1 寻找其中重复的数字
// 解法1：排序 + 遍历
// 解法2：哈希统计

#include <iostream>
#include <vector>

// 解法3：时间复杂度O(N), 空间复杂度O(1)
bool FindRepeatedNumber1(std::vector<int> &number, int *ret)
{
    // 计算个数
    int length = number.size();

    // 没有元素
    if (length == 0)
        return false;
    // 判断数据是否在正确范围
    for (size_t i = 0; i < length; i++)
    {
        if (number[i] < 0 || number[i] > length - 1)
            return false;
    }

    // 判断是否有重复元素
    for (size_t i = 0; i < length; i++)
    {
        // 一直交换直到i位置为指定元素为止
        // 每一次交换其实都是把一个元素放到了指定的为止上，所以说这两层for循环最多也就是遍历了一遍该数组
        while (number[i] != i)
        {
            if (number[i] == number[number[i]])
            {
                *ret = number[i];
                return true;
            }
            std::swap(number[i], number[number[i]]);
        }
    }
    return false;
}

// 有n+1个元素，元素的值范围在1 ~ n 寻找其中重复的数字
// 解法4：不移动元素的基础上，做到空间复杂度为O(1)的解法, 但时间复杂度是O(NlogN)
int CountRange(std::vector<int>& number, int start, int end)
{
    int count = 0;
    for(size_t i = 0; i < number.size(); i++)
    {
        if(number[i] >= start && number[i] <= end)
            count++;
    }
    return count;
}

int FindRepeatedNumber2(std::vector<int> &number)
{
    // 计算个数
    int length = number.size();

    // 没有元素
    if (length == 0)
        return -1;
    // 判断数据是否在正确范围
    for (size_t i = 0; i < length; i++)
    {
        if (number[i] < 0 || number[i] > length - 1)
            return -1;
    }
    
    int start = 1;
    int end = length - 1;
    while(end >= start)
    {
        //计算中间位置
        int middle = ((end - start) >> 1) + start;
        //计算范围内出现的个数
        int count = CountRange(number, start, middle);
        if(start == end)
        {
            if(count > 1)
                return start;
            else 
                break;
        }
        if(count > (middle - start + 1))
            end = middle;
        else 
            start = middle + 1;
    }
    return -1;
}

int main()
{
    std::vector<int> num1 = {2, 3, 5, 4, 3, 2, 6, 7};
    int ret = -1;
    std::cout << FindRepeatedNumber1(num1, &ret) << std::endl;
    std::cout << ret << std::endl
              << std::endl;

    std::vector<int> num2 = {2, 3, 5, 4, 3, 2, 6, 7};
    std::cout << FindRepeatedNumber2(num2) << std::endl;
    return 0;
}